#include <stdio.h>
#include <stdlib.h>
#include "common.h"

// 堆筛选调整
void sift(int R[], int low, int high) {
    int i = low, j = 2 * i;  // R[j]是R[i]的左孩子
    int tmp = R[i];  // 双亲结点有可能会发生置换，所以在置换之前先保留
    while (j <= high) {
        if (j < high && R[j] < R[j + 1]) {  // 若右孩子较大，把j指向右孩子
            j++;
        }
        if (tmp < R[j]) {  // 若根结点小于最大孩子的关键字
            R[i] = R[j];  // 将R[j]调整到双亲结点位置上
            i = j;        // 修改i和j值，以便继续向下筛选
            j = 2 * i;
        }
        else break;  // 若根结点大于等于最大孩子关键字，筛选结束
    }
    R[i] = tmp;  // 被筛选结点放入最终位置上
}

// 堆排序
void HeapSort(int R[], int n) {
    int i;
    // 构建初始堆
    for (i = n / 2; i >= 1; i--) {
        sift(R, i, n);
    }
    // 堆排序
    for (i = n; i > 1; i--) {  
        // 交换堆顶和末尾元素
        swap(&R[1], &R[i]);
        sift(R, 1, i - 1);  // 重新调整堆
    }
}

// 打印数组
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 打印数组（1-based）
void PrintArray1Based(int arr[], int n) {
    for (int i = 1; i <= n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 检查数组是否已排序
int IsSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            return 0;  // 未排序
        }
    }
    return 1;  // 已排序
}

// 复制数组
void CopyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试堆排序函数
void TestHeapSort(int original[], int n, const char* testName) {
    printf("=== %s ===\n", testName);
    printf("原始数组: ");
    PrintArray(original, n);
    
    // 测试HeapSort函数（使用1-based索引）
    int arr[n + 1];  // 1-based索引
    arr[0] = 0;  // 占位符，不使用索引0
    for (int i = 1; i <= n; i++) {
        arr[i] = original[i-1];
    }
    
    HeapSort(arr, n);
    printf("排序后结果: ");
    PrintArray1Based(arr, n);
    
    // 检查正确性（将1-based转换为0-based检查）
    int temp_check[n];
    for (int i = 0; i < n; i++) {
        temp_check[i] = arr[i + 1];
    }
    printf("排序正确性: %s\n", IsSorted(temp_check, n) ? "✓ 正确" : "✗ 错误");
    printf("\n");
}

// 主测试函数
void TestHeapSortComprehensive() {
    printf("========== HeapSort 函数测试 ==========\n\n");
    
    // 测试用例1：一般情况
    int test1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(test1) / sizeof(test1[0]);
    TestHeapSort(test1, n1, "测试1：一般情况");
    
    // 测试用例2：已排序数组
    int test2[] = {1, 2, 3, 4, 5};
    int n2 = sizeof(test2) / sizeof(test2[0]);
    TestHeapSort(test2, n2, "测试2：已排序数组");
    
    // 测试用例3：逆序数组
    int test3[] = {5, 4, 3, 2, 1};
    int n3 = sizeof(test3) / sizeof(test3[0]);
    TestHeapSort(test3, n3, "测试3：逆序数组");
    
    // 测试用例4：重复元素
    int test4[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n4 = sizeof(test4) / sizeof(test4[0]);
    TestHeapSort(test4, n4, "测试4：重复元素");
    
    // 测试用例5：单个元素
    int test5[] = {42};
    int n5 = sizeof(test5) / sizeof(test5[0]);
    TestHeapSort(test5, n5, "测试5：单个元素");
    
    // 测试用例6：两个元素
    int test6[] = {2, 1};
    int n6 = sizeof(test6) / sizeof(test6[0]);
    TestHeapSort(test6, n6, "测试6：两个元素");
}

// 主函数
int main() {
    TestHeapSortComprehensive();
    return 0;
}
